package 力扣;
import java.util.*;

public class N皇后 {
    static List<List<String>> sloves;
        public static void main(String[] args) {
            System.out.print("请N皇后问题得N的个数：");
            Scanner scanner = new Scanner(System.in);
            // int max = 8;//max表示n个皇后
            int max = scanner.nextInt();
            //        用array[n]表示：皇后在第n+1行,array[n]列。比如array[0] = 8
            //        意思为:该皇后位于第1行第8列的坐标;
            int array[] = new int[max];
            sloves = new ArrayList<>();
            new N皇后().backtrack(0,max,array);

            System.out.println(sloves);
        }
        //核心代码
        public void backtrack(int n,int max,int []array) {
            if (n == max) {//层数：n,从零开始。  深度：max 。 n==max表示遍历完叶子节点

                print(array,max);
                return;
            } else {
                for (int i = 1; i <=max; i++) {//第n层的第i列，要明白当前属于是哪一层！ 即搜索或回溯到了哪一层了！
                    array[n] =i;//array[n]表示的就是第n层第i列，即皇后的坐标
                    if (nice(n,array)) {
                        backtrack(n + 1,max,array);//类似于n重for循环，只不过变成递归版的
                    }
                }
            }

        }

        public boolean nice(int n,int []array) {
            for (int i = 0; i < n; i++) {//前i层: 跟之前已经确定的 皇后的位置进行比较
                //   System.out.println(array[i]==(i+1));
                if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    // if (array[n]==array[i])
//                    if (n!=i)
                    return false;
                }
                if(array[i]==array[n]){//保证了列值的不重复
                    return false;
                }
            }
            return true;
        }
        int k = 0;
        public void print(int []array,int max) {
            char[][] a=new char[max][max];
            List<String> strings = new ArrayList<String>();
            for (int i = 0; i <max; i++) {
                char[] chars = new char[max];
                Arrays.fill(chars, '.');//数组填充
                chars[array[i]-1]='Q';
                strings.add(String.valueOf(chars));
            }
            sloves.add(strings);
        }

}
